package LeetCode;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}15:03
 */
public class LeetCode134 {

    public static void main(String[] args) {
        int[] gas = {2,3,4};
        int[] cost = {3,4,3};
        System.out.println(canCompleteCircuit(gas, cost));
    }

    public int canCompleteCircuit2(int[] gas, int[] cost) {
        // 加油站起始点
        int start = 0;
        // 从0-start需要补充多少油
        int total = 0;
        // 从start开始到i 油量
        int tank = 0;

        for(int i=0; i<gas.length; i++) {
            // 走过ith 加油站还剩下多少油 （>0）
            // 要走ith 加油站差多少油 （<0）
            tank += gas[i] - cost[i];
            // 油不够了，start不能做起始点；
            // 且start ～ i 都不可做起始点。
            if(tank < 0) {
                start = i+1;
                total += tank;
                tank = 0;
            }
        }
        return total+tank >= 0 ?start : -1;
    }

    public static int canCompleteCircuit(int[] gas, int[] cost) {
        //重0为起点开始出发
        if (gas==null||cost==null){
            return -1;
        }
        int temp = 0;
        for (int i = 0; i < gas.length; i++) {
            int gasValue = 0;
            int statrIndex = i;
            temp = statrIndex;
            while (true) {
                gasValue += gas[statrIndex];//得到了汽油
                statrIndex = (statrIndex + 1) % gas.length;//进行一次位移
                if ((statrIndex - 1) % cost.length == -1) {
                    gasValue -= cost[cost.length - 1];
                } else {
                    gasValue -= cost[(statrIndex - 1) % cost.length];
                }
                if (gasValue < 0) {
                    break;
                }
                if (statrIndex == temp) {
                    return temp;
                }
            }
        }
        return -1;
    }
}
